package com.wang;

import java.util.Arrays;

/**
 * @author yandong
 */
public class HeapSort {
    // arr是待排序数组, n是arr.length
    public void heapSort(int[] arr) {
        int n = arr.length;
        // 1.构建大根堆 (从最后一个非叶子节点向前调整)
        for (int i = n/2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, n);
        }

        // 2.堆排序 (每次将堆顶元素与最后一个元素交换,然后重新调整堆)
        for (int i = n-1; i > 0; i--) {
            // 将堆顶元素与堆最后一个元素交换
            swap(arr, 0, i);
            // 调整剩余元素为大根堆 (此时堆大小为i)
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 调整堆 (将元素i位置的元素与左右子节点进行比较,将较大的子节点与i位置的元素交换)
     * @param arr 待排序数组
     * @param i 根节点索引
     * @param n 堆大小
     */
    private void adjustHeap(int[] arr, int i, int n) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(arr, i, largest);
            adjustHeap(arr, largest, n);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{8, 11, 3, 2, 0, 67, 5, 99, 77};
        new HeapSort().heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
